package com.wtgroup.demo.leetcode.q839_相似字符串组;


import java.util.*;

/**
 * 使用深度优先搜索找出图中的所有连通分量
 *
 * 缺陷: 内存和效率好像不高.
 * ? 「并查集」 ?
 */
public class S_My {

    public static void main(String[] args) {
        // String[] strs = new String[]{"tars", "rats", "arts", "star"};
        String[] strs = new String[]{"kccomwcgcs", "socgcmcwkc", "sgckwcmcoc", "coswcmcgkc", "cowkccmsgc", "cosgmccwkc", "sgmkwcccoc", "coswmccgkc", "kowcccmsgc", "kgcomwcccs"};
        // coswmccgkc
        // cosgmccwkc
        // sgckwcmcoc
        new S_My().numSimilarGroups(strs);
    }

    /**
     * 每个字符串当做节点.
     * Map + Set 来表示节点连接.
     * 寻找独立树的个数, 即结果.
     *
     * */

    public int numSimilarGroups(String[] strs) {
        HashMap<String, Set<String>> graph = new HashMap<>();
        for (String str : strs) {
            Set<String> set1 = graph.computeIfAbsent(str, s -> new HashSet<>());
            for (String k : graph.keySet()) {
                if (k.equals(str)) {
                    continue;
                }
                if (isSimilar(str, k)) {
                    Set<String> set = graph.computeIfAbsent(k, s -> new HashSet<>());
                    set.add(str);
                    set1.add(k);
                }
            }
        }

        System.out.println("graph: ");
        for (Map.Entry<String, Set<String>> entry : graph.entrySet()) {
            System.out.println(entry);
        }

        int count = 0;
        HashSet<String> mark = new HashSet<>();

        // 计算连通分量
        for (String k : graph.keySet()) {
            if (mark.contains(k)) {
                continue;
            }
            count++;
            dfs(graph, k, mark);
        }

        System.out.println("count: " + count);
        return count;
    }

    private void dfs(Map<String, Set<String>> graph, String k, Set<String> mark) {
        if (mark.contains(k)) {
            return;
        }

        mark.add(k);
        Set<String> children = graph.get(k);
        if (children!=null && children.size()>0) {
            for (String child : children) {
                dfs(graph, child, mark);
            }
        }
    }

    /**
     * 要求: 异位词. 长度相同, 字符一样, 只是顺序可能不一样.
     * 最多两处字符不一样.
     * @param a
     * @param b
     * @return
     */
    private boolean isSimilar(String a, String b) {
        char[] aa = a.toCharArray();
        char[] bb = b.toCharArray();
        int k = 0;
        for (int i = 0; i < aa.length; i++) {
            if (k>2) {
                break;
            }
            if (aa[i] != bb[i]) {
                k++;
            }
        }
        return k <= 2;
    }
}
